package main

import (
	"fmt"
	"math"
	"strings"
)

func main() {
	var M = math.Inf(1)
	var matrix = [][]float64{
		//A  B  C  D  E  F
		{0, 10, M, 4, M, M}, //A
		{10, 0, 8, 2, 6, M}, //B
		{M, 8, 0, 15, 1, 5}, //C
		{4, 2, 15, 0, 6, M}, //D
		{M, 6, 1, 6, 0, 12}, //E
		{M, M, 5, M, 12, 0}, //F
	}
	nodeNames := map[int]string{
		0: "A",
		1: "B",
		2: "C",
		3: "D",
		4: "E",
		5: "F",
	}
	for i := 0; i < len(matrix); i++ {
		distance, path := dijkstra(matrix, i)
		fmt.Printf("起始节点:%s 到其他点距离：%v, 路径图:%v\n", nodeNames[i], distance, path)
		for j := 0; j < len(matrix); j++ {
			pathLine := []string{nodeNames[j]}
			for prev := j; path[prev] != -1; {
				prev = path[prev]
				pathLine = append([]string{nodeNames[prev]}, pathLine...)
			}
			fmt.Printf("\t起始节点%s->%s，距离:%d，需要经过路径: %s\n", nodeNames[i], nodeNames[j], int(distance[j]), PathLine(pathLine))
		}
	}
}

type PathLine []string

func (p PathLine) String() string {
	sb := new(strings.Builder)
	for i := 0; i < len(p); i++ {
		if i > 0 {
			sb.WriteString("->")
		}
		sb.WriteString(p[i])
	}
	return sb.String()
}

func dijkstra(matrix [][]float64, start_node int) ([]float64, []int) {
	var M = math.Inf(1)
	matrix_length := len(matrix)
	distance := make([]float64, matrix_length)
	used_node := make([]bool, matrix_length)
	path := make([]int, matrix_length)
	for i := 0; i < matrix_length; i++ {
		distance[i] = M
		path[i] = -1
	}
	distance[start_node] = 0

	for i := 0; i < matrix_length; i++ {
		min_value := M
		min_value_index := matrix_length
		for i := 0; i < matrix_length; i++ {
			if !(used_node[i]) && distance[i] < min_value {
				min_value = distance[i]
				min_value_index = i
			}
		}
		if min_value == M {
			break
		}
		used_node[min_value_index] = true
		for i := 0; i < matrix_length; i++ {
			if v := distance[min_value_index] + matrix[min_value_index][i]; v < distance[i] {
				distance[i] = v
				path[i] = min_value_index
			}
		}
	}

	return distance, path
}
